1. Field of the Invention
The present invention relates to the RSA cryptography algorithm and in particular to the generation of RSA keys. The RSA cryptosystem, named after its inventors R. Rivest, A. Shamir and L. Adleman, is one of the most widespread public key cryptosystems. It can be used both for obtaining secrecy and for generating digital signatures. Its security is based on the fact that the so-called integer factorization problem cannot be solved presently in algorithmically efficient manner.
2. Description of the Related Art
Before dealing with the RSA cryptosystem in more detail, some basic terms of cryptography shall be outlined first. Generally, a distinction is made between symmetric encryption systems, also referred to as secret key encryption systems, and public key encryption systems.
A communication system with two parties making use of encryption by means of symmetric keys, can be described as follows. The first party communicates its encryption key to the second party via a secure channel. The first party then encrypts the secret message by means of the key and transmits the encrypted message to the second party via a public or non-secured channel. The second party then decrypts the encrypted message by use of the symmetric key that was communicated to the second party via the secure channel. An essential problem with such encryption systems resides in providing an efficient way of exchanging the secret keys, i.e. of finding a secure channel.
In contrast thereto, asymmetric encryption is carried out as follows. A party desiring to receive a secret message communicates its public key to the other party, i.e. the party from which it desires to receive a secret message. The public key is communicated via a non-secured channel, i.e. via a “public” channel.
The party desiring to send a secret message receives the public key of the other party, encrypts the message using the public key and transmits the encrypted message again via a non-secured channel, and thus a public channel, to the party from which the public key was sent. Only the party that generated the public key is capable of making available a private key for decrypting the encrypted message. Not even the party that encrypted its message using the public key is in the position of decrypting the message. An advantage of this concept consists in that no secure channel, and thus no secret exchange of keys, is required between the two parties. The party that decrypted the message need not and must not know the private key of the message recipient.
A physically analogous scheme to the asymmetric encryption concept or the public key encryption concept can be outlined as follows. Consider a metal box with a lid secured by a combination lock. The combination is known only to the party desiring to receive an encrypted message. If the lock is left open and made available to the public, anybody desiring to communicate a secret message may place this message in the metal box and close the lid. However, only the party providing the box knows the combination of the combination lock. Only this latter party is in the position to decrypt the message, i.e. to reopen the metal box. Even the party that placed the message in the box can no longer retrieve the same.
Essential for asymmetric or public key encryption concepts is the underlying mathematical problem the solution of which is nearly impossible utilizing the public key for decryption, but the solution of which is easily possible knowing the private key. One of the most common public key cryptosystems is the RSA cryptosystem. The RSA cryptosystem is described in the “Handbook of Applied Cryptography”, Menezes, van Oorschot, Vanstone, CRC Press 1997, pages 285 to 291.
The first task consists in generating the keys for the RSA cryptosystem. To this end, reference is made to FIG. 3. An entity that is to receive an encrypted message, in a first step 300 must generate first two large prime numbers p and q that preferably should have about equal quantities. Thereafter, in a step 310, the product of the two prime numbers is calculated, which is also referred to as modulus N. In addition thereto, Euler's φ function is computed, which is equal to the product of (p−1) and (q−1). In a step 320, a random integer e is selected then, with e being selected such that e is greater than 1 and smaller than φ, with the further condition that the greatest common divisor gcd of e and φ is 1, i.e. that e and φ are relatively prime. Thereafter, in a step 330 a number d is computed that has to fulfil the following equation:e×d=1modφd is also referred to as multiplicative inverse with respect to modulus φ and usually is computed using the extended Euclidean algorithm, which is also described in the “Handbook of Applied Cryptography”, page 67. d thus is a unique integer that is greater than 1 and smaller than φ and thus fulfils the equation given.
In a step 340, the public key is then output, with the public key comprising the modulus N and the number e. In contrast thereto, the private key d is not output, but is stored in a step 350 in order to be utilized for decryption when the key-generating entity has received a message that is encrypted using the public key output in step 340.
In the following, reference is made to FIG. 2 in order to illustrate the RSA algorithm. The initial situation is that one communication partner encrypts a message M that has to be decrypted by the other communication partner. The encrypting entity must first receive, in a step 200, the public key (N, e) in order to be able at all to send an encrypted message to the other party. Following this, the encrypting party, in a step 210, has to represent the message to be encrypted in the form of an integer M, with M having to be in the interval from 0 to N−1. In a step 220, which is the encryption step proper, the encrypting entity has to compute the following equation:C=Memod N.
C is the encrypted message. This message is then output in a step 230 and transmitted to the recipient of the encrypted message via a public channel, designated 240 in FIG. 2. The recipient receives the encrypted message C in a step 250 and performs the following computation in a step 260, which is the decryption step proper:M=Cdmod N.
It can be seen from FIG. 2 that only the public key (N, e) is necessary for encryption, but not the private key d, whereas decryption requires the private key d.
The question is now how an attacker can break the RSA cryptosystem. He knows the public key, i.e. N and e. In the same manner as shown in FIG. 3, he could now factorize the modulus N into a product of two prime numbers and then compute the secret key d in the same manner as it was done by the key-generating authentic party. To this end, the attacker would have to try all possible prime number pairs p′, q′ in order to sooner or later hit the private key d in consideration of e. With small prime numbers p and q, this problem is relatively easy to solve simply by trial. However, if p and q, i.e. the modulus N that is the product of p and q, become increasingly greater, the various possibilities for the factorization of modulus N increase to astronomical extents. This is what the security of the RSA system is based on. It can be seen therefrom that secure cryptosystems must make use of very long numbers that may have a length of, for example, 512, 1024 or even up to 2048 bits.
With increasing length of the prime numbers p and q, however, the computation of the multiplicative inverse, i.e. of the private key d in step 330 of FIG. 3, becomes time-critical as well. To this end, the extended Euclidean algorithm is utilized the required computation time of which may also assume considerable orders of magnitude with increasing length of the relevant numbers.